#include <stdlib.h>
#include <stdio.h>

#ifdef TEST
  #define GRID_SIZE 4
  #define SUB_GRID_SIZE 2
#endif

#include "dlx.h"

#define getCandidate(i) ((i)%(GRID_SIZE)+1)
#define getColumn(i)    (((i)%(GRID_SIZE*GRID_SIZE))/GRID_SIZE)
#define getRow(i)       ((i)/(GRID_SIZE*GRID_SIZE))
#define getRegion(i)    ((getRow(i)/SUB_GRID_SIZE)*(GRID_SIZE/SUB_GRID_SIZE)+(getColumn(i)/SUB_GRID_SIZE))
#define linkCellsLR(l, r) ((l)->R)=(r);((r)->L)=(l);
#define linkCellsUD(u, d) ((u)->D)=(d);((d)->U)=(u);
#define iterateRows(i)    for (i = 0; i < GRID_SIZE*GRID_SIZE*GRID_SIZE; i++)
#define iterateColumns(i) for (i = 0; i < 4*GRID_SIZE*GRID_SIZE;         i++)

/* remove node c */
void removeCell(Node c) 
{
  (((c)->L)->R)=((c)->R);
  (((c)->R)->L)=((c)->L);	
  (((c)->U)->D)=((c)->D);	
  (((c)->D)->U)=((c)->U);
}

/* unremove node c */
void insertCell(Node c) 
{
  (((c)->L)->R)=(c);				
  (((c)->R)->L)=(c);
  (((c)->U)->D)=(c);
  (((c)->D)->U)=(c);
}

inline int candidateToRow (int candidate, int row, int column)
{
  return row*GRID_SIZE*GRID_SIZE + column*GRID_SIZE + candidate-1;
}

/* append node N to columnHead c */
static void appendColumn (Node c, Node n)
{
  if (c->D == NULL)
    {
      linkCellsUD(c, n);
      n->D = NULL;
    }
  else
    {
      appendColumn(c->D, n);
    }
}

/* create and initialize new sparse matrix */
SparseMatrix newSparseMatrix(void)
{
  int i;
  int cell, row, column, region, candidate;
  SparseMatrix new = malloc(sizeof(SparseMatrix_T));
  if (new == NULL)
    {
      fprintf(stderr, "ERROR: `newSparseMatrix()' memory allocation failed!\n");
      exit(1);
    }

  /* set root */
  new->root = new->columnHead;

  /* initialize and link rows */
  iterateRows(i)
    {
      new->rowHead[i] = &(new->cells[4*i]);
      new->cells[4*i].L = NULL;
      linkCellsLR(&(new->cells[4*i  ]), &(new->cells[4*i+1]));
      linkCellsLR(&(new->cells[4*i+1]), &(new->cells[4*i+2]));
      linkCellsLR(&(new->cells[4*i+2]), &(new->cells[4*i+3]));

      new->cells[4*i+3].R = NULL;
      new->cells[4*i  ].row = i;
      new->cells[4*i+1].row = i;
      new->cells[4*i+2].row = i;
      new->cells[4*i+3].row = i;

      new->cells[4*i  ].size = 0;
      new->cells[4*i+1].size = 0;
      new->cells[4*i+2].size = 0;
      new->cells[4*i+3].size = 0;
    }

  /* initialize and link column heads*/
  iterateColumns(i)
    {
      new->columnHead[i].column = i;
      new->columnHead[i].size = GRID_SIZE;
      new->columnHead[i].D = NULL;

      if (i < 4*GRID_SIZE*GRID_SIZE-1)
	{
	  linkCellsLR(&(new->columnHead[i]), &(new->columnHead[i+1]));
	}
    }

  /* link columns */
  iterateRows(i)
    {
      row = getRow(i);
      column = getColumn(i);
      region = getRegion(i);
      cell = row*GRID_SIZE + column;
      candidate = getCandidate(i);

      /* cell constraint */
      appendColumn(&(new->columnHead[cell]), &(new->cells[4*i]));
      new->cells[4*i].column = cell;
      /* row constraint */
      appendColumn(&(new->columnHead[row*GRID_SIZE+candidate-1    +   GRID_SIZE*GRID_SIZE]), 
		       &(new->cells[4*i+1]));
      new->cells[4*i+1].column = row*GRID_SIZE+candidate-1    +   GRID_SIZE*GRID_SIZE;
      /* column constraint */
      appendColumn(&(new->columnHead[column*GRID_SIZE+candidate-1 + 2*GRID_SIZE*GRID_SIZE]), 
		       &(new->cells[4*i+2]));
      new->cells[4*i+2].column = column*GRID_SIZE+candidate-1 + 2*GRID_SIZE*GRID_SIZE;
      /* region constraint */
      appendColumn(&(new->columnHead[region*GRID_SIZE+candidate-1 + 3*GRID_SIZE*GRID_SIZE]), 
		       &(new->cells[4*i+3]));
      new->cells[4*i+3].column = region*GRID_SIZE+candidate-1 + 3*GRID_SIZE*GRID_SIZE;
    }

  return new;
}

void delSparseMatrix(SparseMatrix sm)
{
  free(sm);
}


#ifdef TEST
int main()
{
  SparseMatrix sm = newSparseMatrix();
  int i;
  /* for (i = 0; i < GRID_SIZE*GRID_SIZE*GRID_SIZE; i++) */
  /*   { */
  /*     printf("%d: (%d,%d,%d,%d)\n", i, getCandidate(i), getRow(i)+1, getColumn(i)+1, getRegion(i)); */
  /*   } */

  /* iterateRows(i) */
  /*   { */
  /*     printf("%d,%d: %d %d %d %d\n", i, sm->rowHead[i]->row,  */
  /* 	     sm->rowHead[i]->column,  */
  /* 	     sm->rowHead[i]->R->column, */
  /* 	     sm->rowHead[i]->R->R->column, */
  /* 	     sm->rowHead[i]->R->R->R->column); */
  /*   } */

  iterateColumns(i)
  {
    printf("%d,%d,%d: %d %d %d %d\n", i, sm->columnHead[i].column, sm->columnHead[i].size,
  	   sm->columnHead[i].D->row,
  	   sm->columnHead[i].D->D->row,
	   sm->columnHead[i].D->D->D->row,
	   sm->columnHead[i].D->D->D->D->row);
  }

  delSparseMatrix(sm);
  return 0;
}
#endif
